package cn.z2huo.algorithm.binarytree;

import java.util.ArrayDeque;
import java.util.Deque;

// 后序遍历二叉树
public class Traversal_LRD {
    // 递归后序遍历二叉树
    public void recurse(TreeNode root){
        if(root!=null){
            if(root.getLeft()!=null){
                recurse(root.getLeft());
            }
            if(root.getRight()!=null){
                recurse(root.getRight());
            }
            System.out.print(root.toString()+" ");
        }
    }

    // 迭代，利用栈后序遍历二叉树
    public void iterate(TreeNode root){
        Deque<TreeNode> stack = new ArrayDeque();
        TreeNode node = root;
        TreeNode flag = null;
        while(node!=null){
            while(node.getLeft()!=null){
                stack.push(node);
                node = node.getLeft();
            }
            while(node.getRight()==null || node.getRight()==flag){
                System.out.print(node.toString()+" ");
                flag = node;
                if(stack.isEmpty()) return;
                node = stack.pop();
            }
            stack.push(node);
            node = node.getRight();
        }
        System.out.println();
    }
}
